// ***********************************************归并排序********************************************
/**
 * 基本思路：
 * 将一段无序的序列分成若干组，以二路归并排序为例，将其两两分组，组内有序后，再两两合并为四个一组，排序 ……，直到合并成整个序列
 * 稳定的排序，时间复杂度O(nlogn)，空间复杂度O(n)
 */
function mergeSort(arr) {
    mergeSortbyRecursion(arr, 0, arr.length - 1)
}
// 递归定义：将arr数组中起始下标到结束下标中的元素进行排序
function mergeSortbyRecursion(arr, low, high) {
    // low是目标序列起始点下标
    // high是目标序列终点下标
    if (low < high) {
        //折半二分，1组→2组，2组→4组，4组→8组……，直到每组只剩1个就开始融合
        let mid = Math.floor((low + high) / 2)
        mergeSortbyRecursion(arr, low, mid)
        mergeSortbyRecursion(arr, mid + 1, high)
        merge(arr, low, mid, high)
    }
}
//将前后相邻的两个有序表归并为一个有序表
function merge(arr, firstStart, firstEnd, lastEnd) {
    //辅助数组
    let auxArr = new Array(arr.length)
    //拷贝一份
    for (let k = firstStart; k <= lastEnd; k++) {
        auxArr[k] = arr[k]
    }
    let i = firstStart, j = firstEnd + 1, k = i
    //for循环先++再检验判断条件，合并两个有序序列
    for (; i <= firstEnd && j <= lastEnd; k++) {
        if (auxArr[i] <= auxArr[j]) {
            arr[k] = auxArr[i]
            i++
        }
        else {
            arr[k] = auxArr[j]
            j++
        }
    }
    //左侧子序列未完
    while (i <= firstEnd) {
        arr[k] = auxArr[i]
        k++
        i++
    }
    //右侧子序列未完
    while (j <= lastEnd) {
        arr[k] = auxArr[j]
        k++
        j++
    }
}

//测试用例
// let arr = [49,38,65,97,76,13,27]
// mergeSort(arr)
// console.log(arr);


const Node = require('../../数据结构/链表/单链表/node');

// 链表归并排序（无头节点）
// 获去链表中间元素
function getMid(listHead) {
    let fast = listHead,
        slow = listHead;
    while (fast.next !== null && fast.next.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
// 合并两个有序链表
function listMerge(firsthead, lasthead) {
    let auxHead = new Node;
    let p = auxHead;
    let p1 = firsthead;
    let p2 = lasthead;
    while (p1 !== null && p2 !== null) {
        if (p1.data <= p2.data) {
            // p1的小
            p.next = p1;
            p1 = p1.next;
        } else {
            // p2的小
            p.next = p2
            p2 = p2.next
        }
        p = p.next;
    }
    if (p1 !== null) {
        p.next = p1;
    }
    if (p2 !== null) {
        p.next = p2;
    }
    return auxHead.next;
}
// 归并主体
function linkedList_mergeSort(listHead) {
    // 空表或仅有一个元素
    if (listHead === null || listHead.next === null) return listHead;
    // 得到中点指针
    let mid = getMid(listHead);
    // 分割表
    let rightHead = mid.next;
    let leftHead = listHead;
    mid.next = null;
    // 递归分表，全部分为一个一个，返回有序表的表头
    let lnode = linkedList_mergeSort(leftHead);
    let rnode = linkedList_mergeSort(rightHead);
    // 合并有序链表
    return listMerge(lnode, rnode);
}



// 测试用例
let arr = [49, 38, 65,97,76,13,27,100,84,135,846,3,48]
let head = new Node(49);
let p = head;
for (let i = 1; i <= arr.length - 1; i++) {
    p.next = new Node(arr[i]);
    p = p.next;
}
console.log(linkedList_mergeSort(head));
